Search Results

Documents authored by Meesum, S. M.

Found 2 Possible Name Variants:

Meesum, S. M.

Document
DOI: 10.4230/LIPIcs.STACS.2017.32
Matrix Rigidity from the Viewpoint of Parameterized Complexity

Authors: Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
The rigidity of a matrix A for a target rank r over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational Complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of Parameterized Complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of Parameterized Complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in case F equals the reals or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in Real Algebraic Geometry, which are not well known in Parameterized Complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.
Cite as

Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi. Matrix Rigidity from the Viewpoint of Parameterized Complexity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.STACS.2017.32,
  author =	{Fomin, Fedor V. and Lokshtanov, Daniel and Meesum, S. M. and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Matrix Rigidity from the Viewpoint of Parameterized Complexity}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.32},
  URN =		{urn:nbn:de:0030-drops-70019},
  doi =		{10.4230/LIPIcs.STACS.2017.32},
  annote =	{Keywords: Matrix Rigidity, Parameterized Complexity, Linear Algebra}
}

Meesum, Syed M.

Document
DOI: 10.4230/LIPIcs.ESA.2019.1
Constant-Factor FPT Approximation for Capacitated k-Median

Authors: Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski, Syed M. Meesum, and Michał Włodarczyk

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Capacitated k-median is one of the few outstanding optimization problems for which the existence of a polynomial time constant factor approximation algorithm remains an open problem. In a series of recent papers algorithms producing solutions violating either the number of facilities or the capacity by a multiplicative factor were obtained. However, to produce solutions without violations appears to be hard and potentially requires different algorithmic techniques. Notably, if parameterized by the number of facilities k, the problem is also W[2] hard, making the existence of an exact FPT algorithm unlikely. In this work we provide an FPT-time constant factor approximation algorithm preserving both cardinality and capacity of the facilities. The algorithm runs in time 2^O(k log k) n^O(1) and achieves an approximation ratio of 7+epsilon.
Cite as

Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski, Syed M. Meesum, and Michał Włodarczyk. Constant-Factor FPT Approximation for Capacitated k-Median. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{adamczyk_et_al:LIPIcs.ESA.2019.1,
  author =	{Adamczyk, Marek and Byrka, Jaros{\l}aw and Marcinkowski, Jan and Meesum, Syed M. and W{\l}odarczyk, Micha{\l}},
  title =	{{Constant-Factor FPT Approximation for Capacitated k-Median}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.1},
  URN =		{urn:nbn:de:0030-drops-111225},
  doi =		{10.4230/LIPIcs.ESA.2019.1},
  annote =	{Keywords: K-median, Clustering, Approximation Algorithms, Fixed Parameter Tractability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact